// #include <iostream>
// #include <cmath>
// using namespace std;
// const int N = 100;
// int arr[N];
// void find()
// {
//     int l, r, k;

//     cin >> l >> r >> k;

//     int sum_r = 0;
//     int sum_l = 0;
    // for (int i = 1; i <= r; i++)
//     {
//         // if (i == l - 1)
//         // {
//         //     sum_l = sum_r;
//         // }
//         sum_r += pow(arr[i], k);
//     }
//     for (int i = 1; i <= l - 1; i++)
//     { 
//         sum_l += pow(arr[i], k);
//     }
//     cout << sum_r - sum_l << endl;
// }
// int main()
// {
//     int n, m;
//     cin >> n >> m;
//     for (int i = 1; i <= n; i++)
//     {
//         cin >> arr[i];
//     }
//     for (int i = 0; i < m; i++)
//     {
//         find();
//     }

//     return 0;
// }

//定义常量p
//定义两个二维数组，分别存储平方数和前缀和
//根据输入值l,r,k，输出对应的区间和

#include <iostream>

using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const ll N = 1e5 + 9;
ll arr[6][N];
ll prefix[6][N];

int main()
{
    //因为输入的数据多，所以要对流进行处理
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[1][i];
    }
    //由于第一行放进来的数字已经是一次方了，我们从第二行开始放其对应二次方的数字，下面以此类推，由于k<=5,我们直接预处理5行这样的数据
    //我们发现次方就是不断用该数的上一个次方乘以一次方
    for (int i = 2; i <= 5; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            arr[i][j] = (arr[i - 1][j] * arr[1][j]) % p;
        }
    }
    //现在我们预处理前缀和
    //我们发现前缀和就是前一项前缀和加上当前下标arr[i][j]
    //1 2 3 4 5 
    //0+1            1+2             1+2+3   1+2+3+4  1+2+3+4+5
    //1,1-1+arr1,0   1,2-1+arr1,2    1,3     1,4      1,5
    for (int i = 1; i <= 5;i++)
    {
        for (int j = 1; j <= n; j++)
        {
            prefix[i][j] = (prefix[i][j - 1] + arr[i][j]) % p;
        }
    }
    while (m--)
    
    {
        int l, r, k;
        cin >> l >> r >> k;

        cout << (prefix[k][r] - prefix[k][l - 1] + p) % p << endl;//可能为负数所以加上p
    }
    return 0;
}